EVENTO
Algoritmos Baseados em Cadeias de Markov Quânticas
Tipo de evento: Seminário de Avaliação - Série A
As cadeias de Markov quânticas como passeios quânticos são uma ferramenta importante no desenvolvimento de algoritmos quânticos eficientes. Existem passeios quânticos a tempo contínuo e a tempo discreto. Em tempo discreto diferentes formalismos foram desenvolvidos. O formalismo de Szegedy, por exemplo, não utiliza moeda e permite desenvolver algoritmos de busca em um conjunto de elementos marcados. O tempo de alcance está associado a complexidade de algoritmos de busca espacial em grafos. O tempo de alcance quântico, sob certas premissas, possui ganho quadrático em relação ao clássico. Neste contexto, analisamos analiticamente o formalismo de Szegedy no ciclo, obtendo expressões para o tempo de alcance quântico e para a probabilidade de encontrarmos um elemento marcado. Além disso, estendemos o resultado de Szegedy, referente ao ganho quadrático do tempo de alcance quântico, para o caso de cadeias de Markov quânticas descoerentes. Através de um modelo de descoerência inspirado em percolação, definimos o tempo de alcance quântico descoerente e estabelecemos um intervalo da intensidade de descoerência em que o tempo de alcance quântico descoerente é quadraticamente menor que o clássico. O problema de detecção sob ação da descoerência continua com ganho quadrático para o mesmo intervalo. Simulações da descoerência para o grafo completo e ciclo também são analisadas.
Data Início: 13/12/2013 Hora: 10:00 Data Fim: 13/12/2013 Hora: 12:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Raqueline Azevedo Medeiros Santos - University of Latvia -
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Franklin de Lima Marquezino - Universidade Federal do Rio de Janeiro - UFRJ/COPPE Marcelo Dutra Fragoso - Laboratório Nacional de Computação Científica - LNCC Paulo Antonio Andrade Esquef - Laboratório Nacional de Computação Científica - LNCC
